/*
Date:20210509 14:35PM
key:简单dp，三变量较为麻烦
*/
class Solution {
public:
    void swap(int&a,int&b)
    {
        if(a!=b)
        {
            a=a^b;
            b=a^b;
            a=a^b;
        }
    }
    int fib(int n) 
    {
        int*dp=new int[n+1];
        for(int i=0;i<=n;i++)
        {
            if(i<=1){dp[i]=i;}
            //if(i==2){dp[i]=;}
            else{dp[i]=(dp[i-1]+dp[i-2])%(1000000007);}
            //cout<<dp[i];
        }
        return dp[n];
        // int a,b,c,i;
        
        // for(i=0;i<n;i++)
        // {
        //     if(i==0)
        //     {
        //         a=0;
                
        //     }
        //     else
        //     {
        //         if(i==1)
        //         {
        //             b=1;
        //         }
        //         else
        //         {
        //             if(i==3)
        //             {c=a+b;}
        //             else
        //             {
        //                 swap(a,b);
        //                 swap(c,b);
        //                 c=a+b;
        //             }
        //         }
        //     }
        // }
        // if(i==0){return a;}
        // if(i==1){return b;}
        // else
        // {
        //     return c;
        // }
    }
};